package leetcode.sword;

import datastruct.tree.TreeNode;
import leetcode.hot100.Solution297;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Solution37 {
    //剑指offer，序列化二叉树

    public static void main(String[] args) {

        Solution297 s297 = new Solution297();
        Solution37 s37 = new Solution37();

        //构建树
        TreeNode root = s297.deserialize("1,2,null,null,3,4,null,null,5,null,null");
        //序列化
        String ss = s37.serialize(root);
        System.out.println(ss);
        //反序列化
        TreeNode rootNew = s37.deserialize(ss);
        //验证
        System.out.println(s37.serialize(rootNew));
    }

    // Encodes a datastruct to a single string.
    public String serialize(TreeNode root) {
        //扩展层次遍历：把节点的null也遍历到, val1+","+val2+","+...
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(cur==null) sb.append("null,");
            else {
                sb.append(cur.val);
                sb.append(",");
                queue.offer(cur.left);
                queue.offer(cur.right);
            }
        }
        return sb.toString();
    }

    // Decodes your encoded data to datastruct.
    public TreeNode deserialize(String data) {
        String[] vals = data.split(",");
        Queue<String> queue = new LinkedList<>(Arrays.asList(vals)); //存储所有节点
        Queue<TreeNode> needChild = new LinkedList<>(); //存储孩子还没赋值但本节点已被创建的节点

        String rootVal = queue.poll();
        if("null".equals(rootVal)) return null;

        //初始化
        TreeNode root = new TreeNode(Integer.parseInt(rootVal));
        needChild.offer(root);

        while (!needChild.isEmpty()){
            TreeNode curNode = needChild.poll();
            //左节点
            String leftVal = queue.poll();
            if(!"null".equals(leftVal)){
                curNode.left = new TreeNode(Integer.parseInt(leftVal));
                needChild.offer(curNode.left);
            }
            //右节点
            String rightVal = queue.poll();
            if(!"null".equals(rightVal)){
                curNode.right = new TreeNode(Integer.parseInt(rightVal));
                needChild.offer(curNode.right);
            }
        }
        return root;
    }
}
